#include "graph.h"
#include <stdio.h>
#include <queue>
#include <unordered_set>
#include <functional>

using namespace std;

class CmpGraph: public Graph {
public:
    vector<int> cbd;
    bool cmp_split(void);
};

bool CmpGraph::cmp_split(void) {
    cbd = vector<int>(lv.size(), -1);
    queue<int> vq;
    for(int i=0; i<lv.size(); i++) {
        if(cbd[i] != -1) continue;
        cbd[i] = 0;
        vq.push(i);
        while(!vq.empty()) {
            int u = vq.front();
            vq.pop();
            for(auto it=lv[u].begin(); it!=lv[u].end(); it++) {
                if(cbd[*it] != -1) {
                    if((cbd[*it]+cbd[u])&0x1 == 0) 
                        return false;
                }else {
                    cbd[*it] = cbd[u]+1;
                    vq.push(*it);
                }
            }
        }
    }
    return true;
}

void glv_circle_walk(Graph &g, int s) {
    printf("%d", s);
    for(auto it=g.lv[s].begin(); it!=g.lv[s].end(); it++) {
        if(s < *it && g.bdmpre[*it]!=s) {
            printf("->%d->%d", *it, s);
        }
    }
    for(auto it=g.lv[s].begin(); it!=g.lv[s].end(); it++) {
        if(g.bdmpre[*it]==s) {
            printf("->");
            glv_circle_walk(g, *it);
        }
    }
    if(g.bdmpre[s]!=-1) printf("->%d", g.bdmpre[s]);
}


int main(void) {
    Graph g;

    puts("Exercise 22.1:");
    puts("g.lv2mtx(g.lv_trim()):");
    g.lv = { //有向图,带有冗余边和自循环边
        {1, 0, 1},
        {0, 2, 2},
        {1, 1, 1}
    };
    g.lv_trim();
    g.lv2mtx();
    g.mtx_print();

    puts("g.lv_trans(g.mtx2lv()):");
    g.mtx = {
        {0, 1, 1, 0, 0, 0, 0},
        {0, 0, 0, 1, 1, 0, 0},
        {0, 0, 0, 0, 0, 1, 1},
        {0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0}
    };
    g.mtx2lv();
    Graph gt; gt.lv = g.lv_trans();
    gt.lv_print();
    
    puts("g.mtx_square():");
    gt.mtx = g.mtx_square();
    gt.mtx_print();
    
    gt.mtx = gt.mtx_trans();
    printf("g.mtx_trans(g.mtx_square()) has universal sink: %s\n",
            gt.mtx_has_usink() ?"true": "false");
    printf("g.mtx_trans(g.mtx_square()) has universal sink0: %s\n",
            gt.mtx_has_usink0() ?"true": "false");

    puts("\nExercise 22.2-1:");
    /**************** 
    *1 2 3 4 5 6
    *0 1 2 3 4 5   
    ****************/
    g.lv = {
        {1, 3},
        {4},
        {4, 5},
        {1},
        {3},
        {5}
    };
    g.lv_bfs(2);
    g.fvc = '1';
    for(int i=0; i<6; i++) {
        if(g.lv_spath_printc(2, i))
            printf(", d: %d\n", g.bd[i]);
        else 
            putchar('\n');
    }
 
       
    puts("\nExercise 22.2-7:");
    CmpGraph cg;
    cg.lv = {
        {1, 2},  
        {0, 3, 4},
        {0, 5, 6, 3}, 
        {1, 2}, 
        {1},
        {2}, 
        {2} 
    };
    
    
    if(cg.cmp_split()) {
        for(int i=0; i<g.lv.size(); i++) {
            printf("%2d: %2d\n", i, cg.cbd[i]&0x1);   
        }
    }else {
        printf("no way\n");
    }

    puts("Exercise 22.2-8:");
    g.lv = {
        {1, 5, 2},
        {0, 7, 3},
        {0},
        {1, 6},
        {6},
        {0},
        {3, 4},
        {1, 8},
        {7, 9},
        {8}
    };
    int dv2 = g.lv_cag_mlsp();
    puts("树的一条直径:");
    g.lv_spath_print(g.dv, dv2);
    printf("\n直径长度: %d\n", g.bd[dv2]);

    puts("Exercise 22.2-9:");
    g.lv[2].push_back(5);
    g.lv[5].push_back(2);
    g.lv_bfs(0);
    glv_circle_walk(g, 0);
    
    
    puts("\nExercise 22.3-2: ");
    /*************
    * q r s t u v w x y z
    * 0 1 2 3 4 5 6 7 8 9
    **************/
    g.lv = {
        {2, 3, 6},  //0
        {4, 8},     //1
        {5},        //2
        {7, 8},     //3
        {8},        //4
        {6},        //5
        {2},        //6
        {9},        //7
        {0},        //8
        {7}         //9
    };
    g.fvc = 'q';
    //g.lv_dfs_nor();
    g.lv_dfs();
    for(int i=0; i<g.lv.size(); i++) {
        for(auto j=g.head[i]; ~j; j=g.ev[j][1]) {
            char const *et;
            switch(g.etv[j]) {
            case GETREE:
                et = "树边";
                break;
            case GEFRONT:
                et = "前向边";
                break;
            case GEBACK:
                et = "后向边";
                break;
            default :
                et = "横向边";
                break;
            }
            printf("%c->%c: %s\n", i+g.fvc, g.ev[j][0]+g.fvc, et);
        }
    }


    
    puts("\nExercise 22.5-2: ");
    vector<int> vcc = g.lv_strong_con_compts();
    Glv clv(g.lv.size());
    for(int i=0; i<vcc.size(); i++) {
        printf("%c.cc: %d\n", i+g.fvc, vcc[i]);
        clv[vcc[i]].push_back(i);
    }
    for(int i=0; i<clv.size() && clv[i].size()>0; i++) {
        printf("%d: ", i);
        for(auto it=clv[i].begin(); it != clv[i].end(); it++) {
            printf("%c ", g.fvc+*it);
        }
        putchar('\n');
    }    

    puts("\nExercise 22.5-5: ");
    using Et = array<int, 2>;
    hash<int> hash_int;
    auto et_hash = [&hash_int](Et const &a) -> size_t {
        return hash_int(a[0])^hash_int(a[1]);
    };
    auto et_equal = [](Et const &a, Et const &b) -> bool {
        return a[0]==b[0] && a[1]==b[1];
    };
    unordered_set<Et, decltype(et_hash), decltype(et_equal)> 
    eset(vcc.size(), et_hash, et_equal);
    int mcid = 0;
    for(int i=0; i<vcc.size(); i++) 
        mcid = vcc[i]>mcid ?vcc[i]: mcid;
    Graph ccg; ccg.lv.resize(mcid+1);
    for(int i=0; i<g.lv.size(); i++) {
        for(auto it=g.lv[i].begin(); it!=g.lv[i].end(); it++) {
            if(vcc[i]==vcc[*it] || 
               eset.find(Et{vcc[i], vcc[*it]})!= eset.end()) 
                continue;
            eset.insert(Et{vcc[i], vcc[*it]});
            ccg.lv[vcc[i]].push_back(vcc[*it]);  
        }
    }
    ccg.lv_print();
    puts("\nExercise 22.4-1: ");
    /*************
    * m n o p q r s t u v w  x  y  z
    * 0 1 2 3 4 5 6 7 8 9 10 11 12 13
    **************/    
    g.lv = {
        {4, 5, 11},  //0
        {2, 4, 8},     //1
        {5, 6, 9},        //2
        {2, 6, 13},     //3
        {7},        //4
        {8, 12},        //5
        {5},        //6
        {},        //7
        {7},        //8
        {10, 11},         //9
        {13},           //10
        {},           //11
        {9},           //12
        {}           //13
    };
    printf("simple paths from s to t: %d\n", g.lv_dag_simle_paths(6, 7));
    for(int i=0; i<g.tporder.size(); i++) {
        printf("%c ", 'm'+g.tporder[i]);
    }
    puts("\nMST-KRUSKAL:");
    /**************
    *a  b  c  d  e  f  g  h  i 
    *0  1  2  3  4  5  6  7  8   
    **************/
    g.lv = {
        {1, 7},
        {0, 2, 7},
        {1, 3, 5, 8},
        {2, 4, 5},
        {3, 5},
        {2, 3, 4, 6},
        {5, 7, 8},
        {0, 1, 6, 8},
        {2, 6, 7}
    };
    g.wcm = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},   //0
        {0, 0, 8, 0, 0, 0, 0, 11, 0},  //1 
        {0, 0, 0, 7, 0, 4, 0, 0, 2},   //2
        {0, 0, 0, 0, 9, 14, 0, 0, 0},  //3
        {0, 0, 0, 0, 0, 10, 0, 0, 0},  //4
        {0, 0, 0, 0, 0, 0, 2, 0, 0},  //5
        {0, 0, 0, 0, 0, 0, 0, 1, 6},   //6
        {0, 0, 0, 0, 0, 0, 0, 0, 7},   //7
        {0, 0, 0, 0, 0, 0, 0, 0, 0},   //8
    };
    g.fvc = 'a';
    double mtw = 0;
    Glv mlv =  g.lv_mst_kruskal();
    for(auto i=0; i<mlv.size(); i++) {
        printf("%c: ", 'a'+i);
        for(auto it=mlv[i].begin(); it!=mlv[i].end(); it++) {
            printf("%c ", 'a'+*it);
            if(i < *it)
                mtw += g.wcm[i][*it];
        }
        putchar('\n');
    }
    printf("MST Weight: %f\n", mtw);
    puts("MST-PRIM:");
    mtw = 0;
    g.lv_mst_prim(0);
    for(int i=0; i<g.lv.size(); i++) {
        g.lv_spath_printc(0, i);
        if(g.mtpwv[i] < 1e64) 
            mtw += g.mtpwv[i];
        putchar('\n');
    }
    printf("MST Weight: %f\n", mtw);

    puts("\nExercise 24.1-1: ");
    /**************
    *t y z s x
    *0 1 2 3 4
    *注意题中最后(x,t)这条边最后处理未提及
    **************/
    g.lv = {
        {4, 1, 2},
        {4, 2},
        {4, 3},
        {0, 1},
        {0}
    };
    g.wcm = {
        {0,  8, -4,  0,  5},
        {0,  0,  9,  0, -3},
        {0,  0,  0,  2,  7},
        {6,  7,  0,  0,  0},
        {-2,  0,  0,  0,  0}
    };   
    if(g.lv_msp_bf(2)) {
        for(int i=0; i<5; i++) {
            g.lv_spath_print(2, i);
            printf(", mpw: %f\n", g.mtpwv[i]);
        }
    }else {
        printf("There is negative circle in g that 2 can arrive!\n");
    }
    printf("set w(z, x)=4, use s as src: \n");
    g.wcm[2][4] = 4;
    if(g.lv_msp_bf(3)) {
        for(int i=0; i<5; i++) {
            g.lv_spath_print(3, i);
            printf(", mpw: %f\n", g.mtpwv[i]);
        }
    }else {
        printf("There is negative circle in g that 3 can arrive!\n");
        for(int i=0; i<5; i++) {
            printf("%d: pre: %d, mw: %f\n", i, g.bdmpre[i], g.mtpwv[i]);
        }
    }

    

   
    puts("\nExercise 24.2-1: ");
    /************
    *r s t x y z
    *0 1 2 3 4 5
    *************/
    g.lv = {
        {1, 2},
        {2, 3},
        {3, 4 ,5},
        {4, 5},
        {5},
        {}
    };
    g.wcm = {
        {0, 5, 3},
        {0, 0, 2, 6},
        {0, 0, 0, 7, 4, 2},
        {0, 0, 0, 0, -1, 1},
        {0, 0, 0, 0, 0, -2},
    }; 
    g.lv_dag_msp(0);
    for(int i=0; i<5; i++) {
        g.lv_spath_print(0, i);
        if(g.mtpwv[i]<1000000)
            printf(", mpw: %10.6f\n", g.mtpwv[i]);
        else 
            printf(", mpw: infinity\n");
            
    }

    puts("\nExercise 24.3-1");
    /**************
    *s t x y z
    *0 1 2 3 4
    ***************/
    g.lv = {
        {1, 3},
        {2, 3},
        {4},
        {1, 2, 4},
        {0, 2}
    };    
    g.wcm = {
        {0, 3, 0, 5},
        {0, 0, 6, 2},
        {0, 0, 0, 0, 2},
        {0, 1, 4, 0, 6},
        {3, 0, 7},
    };
    puts("以s为源点:");
    g.lv_msp_dijkstra(0);
    for(int i=0; i<5; i++) {
        if(g.lv_spath_print(0, i))
            printf(", mpw: %10.6f\n", g.mtpwv[i]);
        else 
            printf(", mpw: infinity\n");
            
    }
    puts("以z为源点:");
    g.lv_msp_dijkstra(4);
    for(int i=0; i<5; i++) {
        if(g.lv_spath_print(4, i))
            printf(", mpw: %10.6f\n", g.mtpwv[i]);
        else 
            printf(", mpw: infinity\n");
            
    }
    
    puts("\nExercise 25.1-1:");
    /******************
    *1 2 3 4 5 6
    *0 1 2 3 4 5
    ******************/
    g.lv = {
        {4},
        {0, 3},
        {1, 5},
        {0, 4},
        {1},
        {1, 2}
    };
    g.wcm = {
        {0, 0, 0, 0, -1, 0},
        {1, 0, 0, 2, 0, 0},
        {0, 2, 0, 0, 0, -8},
        {-4, 0, 0, 0, 3, 0},
        {0, 7, 0, 0, 0, 0},
        {0, 5, 10, 0, 0, 0},
    };
    Awfm mwm = g.lv_amsp();

    printf("  ");
    for(int i=0; i<g.lv.size(); i++) {
       printf("%6d", i+1);
    }
    putchar('\n');
    for(int i=0; i<g.lv.size(); i++) {
        printf("%2d", i+1);
        for(int j=0; j<g.lv.size(); j++) {
            if(mwm[i][j] == g.MaxWeight)
                printf("%6s", "na");
            else
                printf("%6.2f", mwm[i][j]);
        }
        putchar('\n');
    }

    puts("\nExercise 25.2-1:");
    mwm = g.lv_amsp_fw();
    printf("%2s", "");
    for(int i=0; i<g.lv.size(); i++) {
       printf("%3d", i+1);
    }
    putchar('\n');
    for(int i=0; i<g.lv.size(); i++) {
        printf("%2d", i+1);
        for(int j=0; j<g.lv.size(); j++) {
            if(g.amspre[i][j] > -1)
                printf("%3d", g.amspre[i][j]+1);
            else
                printf("%3d", -1);
        }
        putchar('\n');
    }
    
    puts("\nExercise 25.3-1:");
    mwm = g.lv_amsp_johnson();
    printf("%2s", "");
    for(int i=0; i<g.lv.size(); i++) {
       printf("%3d", i+1);
    }
    putchar('\n');
    for(int i=0; i<g.lv.size(); i++) {
        printf("%2d", i+1);
        for(int j=0; j<g.lv.size(); j++) {
            if(g.amspre[i][j] > -1)
                printf("%3d", g.amspre[i][j]+1);
            else
                printf("%3d", -1);
        }
        putchar('\n');
    }
    putchar('\n');
    printf("%2s", "");
    for(int i=0; i<g.lv.size(); i++) {
       printf("%6d", i+1);
    }
    putchar('\n');
    for(int i=0; i<g.lv.size(); i++) {
        printf("%2d", i+1);
        for(int j=0; j<g.lv.size(); j++) {
            if(mwm[i][j] == g.MaxWeight)
                printf("%6s", "na");
            else
                printf("%6.2f", mwm[i][j]);
        }
        putchar('\n');
    }

    puts("\nExercise 26.3-1:");
    /*****************
    *0 1 2 3 4 5
    *s 1 2 3 4 t
    ******************/   
    g.lv = {
        {1, 2},
        {3},
        {1, 4},
        {2, 5},
        {3, 5},
        {}
    };
    g.wcm = {
        {0, 16, 13},
        {0, 0, 0, 12},
        {0, 4, 0, 0, 14, 0},
        {0, 0, 9, 0, 0, 20},
        {0, 0, 0, 7, 0, 4}
    };
    g.lv_mflow_ffek(0, 5);
    for(int i=0; i<g.lv.size(); i++) {
        for(auto it=g.lv[i].begin(); it!=g.lv[i].end(); it++) {
            if(g.fm[i][*it] > 0) {
                printf("%d->%d: %.0f\n", i, *it, g.fm[i][*it]);
            }
        }
    } 
    double mf = 0;
    for(int i=0; i<g.lv.size(); i++) {
        mf += g.fm[0][i]-g.fm[i][0];
    } 
    printf("max flow: %.0f\n", mf);

    puts("\nExercise 26.5:");
    g.lv_mflow_r2f(0, 5);
    for(int i=0; i<g.lv.size(); i++) {
        for(auto it=g.lv[i].begin(); it!=g.lv[i].end(); it++) {
            if(g.fm[i][*it] > 0) {
                printf("%d->%d: %.0f\n", i, *it, g.fm[i][*it]);
            }
        }
    }
    mf = 0;
    for(int i=0; i<g.fm.size(); i++) {
        mf += g.fm[0][i]-g.fm[i][0];
    } 
    printf("max flow: %.0f\n", mf);
      
    return 0;
}
